package lianbiao;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author Stringzhua
 * @Date 2025/10/23 17:59
 * description:循环链表中的哨兵节点
 */
public class SentinelCircularLinkedList {
    // 循环链表节点内部类
    static class Node {
        Integer data;  // 数据域，支持null
        Node next;     // 指向下一个节点的引用

        // 无参构造（用于哨兵节点）
        public Node() {
            this.data = null;
            this.next = null;
        }

        // 有参构造（用于实际数据节点）
        public Node(Integer data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node sentinel;  // 哨兵节点（核心：固定存在，形成循环）

    // 构造方法：初始化哨兵节点形成自闭环
    public SentinelCircularLinkedList() {
        this.sentinel = new Node();
        this.sentinel.next = this.sentinel;  // 哨兵节点的next指向自身，形成空循环
    }

    /**
     * 检查链表是否为空
     * 空链表判定：哨兵节点的next指向自身（无实际节点）
     */
    public boolean isEmpty() {
        return sentinel.next == sentinel;
    }

    /**
     * 在链表头部插入节点（哨兵节点之后）
     * @param data 插入的节点数据
     */
    public void prepend(Integer data) {
        Node newNode = new Node(data);
        // 1. 新节点指向哨兵的原后继节点
        newNode.next = sentinel.next;
        // 2. 哨兵节点指向新节点，完成头插
        sentinel.next = newNode;
    }

    /**
     * 在链表尾部插入节点（哨兵节点之前）
     * @param data 插入的节点数据
     */
    public void append(Integer data) {
        Node newNode = new Node(data);
        Node current = sentinel;

        // 遍历到最后一个实际节点（当前节点的next为哨兵时停止）
        while (current.next != sentinel) {
            current = current.next;
        }

        // 1. 最后一个节点指向新节点
        current.next = newNode;
        // 2. 新节点指向哨兵，维持循环特性
        newNode.next = sentinel;
    }

    /**
     * 删除第一个实际节点（哨兵的后继节点）
     * @return 删除成功返回true，空链表返回false
     */
    public boolean deleteFirst() {
        if (isEmpty()) {
            return false;
        }

        // 哨兵节点跳过第一个实际节点，直接指向其下一个节点
        sentinel.next = sentinel.next.next;
        return true;
    }

    /**
     * 删除指定数据的节点
     * @param data 要删除的节点数据
     * @return 删除成功返回true，未找到/空链表返回false
     */
    public boolean delete(Integer data) {
        if (isEmpty()) {
            return false;
        }

        Node prev = sentinel;       // 前驱节点（从哨兵开始）
        Node current = sentinel.next;  // 当前节点（第一个实际节点）

        // 遍历终止条件：回到哨兵节点（循环结束）
        while (current != sentinel) {
            if (current.data.equals(data)) {
                // 前驱节点跳过当前节点，完成删除
                prev.next = current.next;
                return true;
            }
            prev = current;
            current = current.next;
        }

        return false;  // 未找到目标节点
    }

    /**
     * 遍历链表（从哨兵后继到哨兵）
     * @return 存储节点数据的List集合
     */
    public List<Integer> traverse() {
        List<Integer> result = new ArrayList<>();
        Node current = sentinel.next;

        // 遍历至回到哨兵节点为止
        while (current != sentinel) {
            result.add(current.data);
            current = current.next;
        }

        return result;
    }

    // 主方法：测试带哨兵的循环单链表功能
    public static void main(String[] args) {
        SentinelCircularLinkedList scl = new SentinelCircularLinkedList();

        // 测试空链表
        System.out.println("初始链表是否为空: " + scl.isEmpty());  // true

        // 头部插入元素
        scl.prepend(30);
        scl.prepend(20);
        scl.prepend(10);
        System.out.println("头部插入10,20,30后: " + scl.traverse());  // [10, 20, 30]

        // 尾部插入元素
        scl.append(40);
        scl.append(50);
        System.out.println("尾部插入40,50后: " + scl.traverse());  // [10, 20, 30, 40, 50]

        // 删除第一个节点
        scl.deleteFirst();
        System.out.println("删除第一个节点后: " + scl.traverse());  // [20, 30, 40, 50]

        // 删除指定节点（存在）
        scl.delete(30);
        System.out.println("删除30后: " + scl.traverse());  // [20, 40, 50]

        // 删除指定节点（不存在）
        boolean success = scl.delete(60);
        System.out.println("删除60是否成功: " + success);  // false

        // 清空链表
        scl.deleteFirst();
        scl.deleteFirst();
        scl.deleteFirst();
        System.out.println("清空后是否为空: " + scl.isEmpty());  // true
        System.out.println("清空后遍历: " + scl.traverse());  // []

        // 空链表删除操作
        success = scl.deleteFirst();
        System.out.println("空链表删除第一个节点: " + success);  // false
    }
}